package com.example.demo;

import org.junit.jupiter.api.Test;

public class FirstMissingPositive {

    @Test
    public void test() {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums));
    }

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 第一步：将所有小于等于 0 或者大于 n 的数置为一个特殊的数字 如 n + 1，将无效的数排除
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 第二步：将出现过的正整数对应的数组位置的数变为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第三步：找到第一个正数所在的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果数组中所有位置的数都是负数，那么缺失的最小正整数就是 n + 1
        return n + 1;
    }
}
